A geocode is a geographical location associated with an entity such as a building, structure, parcel, lot, or other geographical region. Often such entities are identified by a street address, in which case the entities are called street-addressable entities. Geocoding is the process that associates a specific geographical location, such as a pair of latitude-longitude coordinates, with the street address or other identifier of the entity. Geocodes help in enhancing our understanding of geographic relationships between addressable entities on streets. Such understanding of geographic relationships is critical in many areas, including insurance underwriting, telecommunications DSL loop qualification, route assignment and dispatching, and municipal sales tax, to name a few.
Methods exist for generating highly accurate geocodes. For example, addresses can be individually surveyed with GPS receivers. Another approach involves merging parcels maps into a Geographic Information System. These approaches, however are very expensive and time-consuming to implement on a large scale. Accordingly, less expensive and more efficient geocoding methods have been developed. These approaches, however, often produce inaccurate geocodes. For example, a conventional geocoding method called Address Interpolation estimates geocodes of addresses along an entire street segment using knowledge of geocodes for just the endpoints of the street segment. Address Interpolation assumes that the street segments are relatively straight, have uniformly spaced street addresses, have buildings of fairly uniform size and are set back a fairly uniform distance back from the street. Provided these assumptions are satisfied, Address Interpolation can accurately estimate geocodes for addresses along each street segment from the segment's endpoint information by linear interpolation. Unfortunately, the above assumptions often fail, and the resulting geocodes are inaccurate.
Address Interpolation typically uses a Street Map database, which is a compilation of start and end point locations of each street segment, along with information describing the range of addresses on the street segment. To generate such a database, only the endpoints of street segments need to be geocoded (e.g., by surveying). The technique is therefore much less expensive than surveying and individually geocoding every address. However, compiling and maintaining a nationwide Street Map Database is a significant undertaking. In some cases, the data is collected and entered into the Street Map Database using errorprone manual techniques, so it is not uncommon to find errors in data purchased from some Street Map Database providers. Thus, if the Street Map database contains errors, such as incorrect endpoint addresses or locations, then the results of Address Interpolation will also be inaccurate.
The above problems with Address Interpolation will now be illustrated in more detail with reference to FIGS. 1-3. FIG. 1 illustrates an example of a street segment 10. The street segment 10 is characterized by a Start or From endpoint 20, an End or To endpoint 30, a left side 25, and a right side 35. Typically, the Start or From endpoint is the endpoint in proximity to numerical addresses that are lower than the numerical addresses in proximity to the End or To endpoint. Typically, a U.S. Street Map Database will store one range of street addresses associated with the left side of a street segment and another range of addresses with right side of a street segment. Typically, all even numbered addresses are on one side (right or left) and odd numbered addresses are on the other side.
Address Interpolation may be used to estimate a location of address number “24” on street segment 10. According to the Street Map Database, addresses on the left side 25 are odd and range from 1 to 99; addresses on the right side 35 are even and range from 2 to 98. Since 24 is even, we know the address is on the right side 35 and calculate where it falls in the interval from 2 to 98, assuming that the street segment is a straight line. Since 24 is ¼ of the way from 2 to 98, we calculate the expected position 36 of address 24 as ¼ of the way from the From endpoint 20 to the To endpoint 30. FIG. 2 illustrates the expected position of address number 24 based on Address Interpolation. Equation 1 may be used to calculate the percent displacement with respect to the To endpoint for an address on the right side of the street:
                                                                                      RT                -                address                                                                                                RT                -                RF                                                            ×          100                =                  Percent          ⁢                                          ⁢          displacement          ⁢                                          ⁢          of          ⁢                                          ⁢          address          ⁢                                          ⁢          from          ⁢                                          ⁢          the          ⁢                                          ⁢          To          ⁢                                          ⁢                      endpoint            .                                              (                  eq          .                                          ⁢          1                )            where RT is the last address in the address range on the right side of the street and RF is the first address in the address range on the right side of the street.
Alternately, equation 2 may be used to calculate the percent displacement with respect to the From endpoint for an address on the right side of the street:
                                                                                      RF                -                address                                                                                                RT                -                RF                                                            ×          100                =                  Percent          ⁢                                          ⁢          displacement          ⁢                                          ⁢          of          ⁢                                          ⁢          address          ⁢                                          ⁢          from          ⁢                                          ⁢          the          ⁢                                          ⁢          From          ⁢                                          ⁢                      endpoint            .                                              (                  eq          .                                          ⁢          2                )            
Address Interpolation estimates the specific location of an address anywhere along a street segment based on information about just the endpoints of the segment. It can yield accurate results, provided various assumptions are valid. In particular, Address Interpolation assumes that the magnitude of the address number is directly proportional to the distance traveled along the street segment; and the street segment is a straight line. Because these assumptions are not always satisfied, inaccurate results are produced. For example, when this Address Interpolation technique is applied to more complex map scenarios, it may produce unacceptable results. For example, FIG. 3 illustrates the result of geocoding a section of Albuquerque, N. Mex. using conventional Address Interpolation. Street segment 50 is a portion of Greene Avenue with a left side 51, a right side 52, a From endpoint 53, and a To endpoint 54. The crosses, such as cross 60, indicate the estimated locations of the homes/buildings. The polygons, such as polygon 81, represent the locations of the parcels, containing the homes/buildings.
In this example, the addresses on the left side 51 and a right side 52 of a street segment 50 were determined by consulting a parcel map and geocoded based on the these address ranges using Address Interpolation. Note that the addresses in this example descend from high to low along the segment. The X's on the left side 51 and a right side 52 of the street, such as X 60, represent the geocoded addresses. The true position of the outermost addresses on each side of the street are indicated by polygons 80, 81, 103 and 104. The geocoded address 60 should correspond to the polygon 81. The displacement of the geocoded address 60 from the polygon 81 suggests that these addresses were poorly geocoded.
In this case, the Street Map Database provided the following address ranges for this segment (of Greene Ave): Left side (LeftFrom=4599, LeftTo=4501) and Right Side (RightFrom=4598, RightTo=4502). In this example, while the address ranges at the To endpoint 54 of the street segment are accurate (RightTo=4502 and LeftTo=4501), the address ranges at the From endpoint 53 are not, due to an error in the database. Interpolated addresses were calculated based on displacement with respect to the To endpoint 54 of the street. This explains why address 4502 is accurately geocoded: since (|RT−4502|)/(|RF−RT|)=0, address interpolation correctly predicts address 4502 is located 0% down the segment starting at the To side, i.e., at the To side. It also explains why address 4552 is inaccurately geocoded: since (|RT−4552|)/(|RF−RT|)˜½, address 4552 is incorrectly interpolated approximately halfway down the segment at X 60, even though it's true location 81 is adjacent to the From endpoint 53.
The above example illustrates how errors in the Street Map database can produce inaccurate geocodes when using Address Interpolation. It is also evident that if the street segment is curved or if the residences are not actually located right next to the street, then the geocodes generated by Address Interpolation will be inaccurate. Other sources of inaccuracies are non-uniform spacing of lots along a street segment, or non-uniform distribution of addresses along a segment.
A method for locating street addresses on a map is disclosed by Anderson in published U.S. patent application Ser. No. 0158668. According to this method, parcel polygons are extracted from parcel maps, the latitude and longitude of the parcel polygons are identified, and then the latitude-longitude couplets are cross-referenced with a property tax-related database to determine the street addresses for the parcels. The accuracy of the results may be verified by overlaying a map containing the geocoded reference points with an orthophotograph. An operator may then visually correct the map to confirm the map features, such as proper identification of the parcel boundaries and the presence and the exact location of structures. This method, however, suffers from the disadvantage that it requires the explicit geocoding of the parcels in latitude and longitude so that the latitude and longitude values can be correlated with the APN (Assessor Parcel Number) or PIN (Parcel Identifier Number) in a property-tax related database. Furthermore, access to parcel maps and property-tax related databases containing reference latitude-longitude couplets associated with street addresses is required. The quality and format of property-tax related databases varies greatly across the United States. Because access to property-tax databases is controlled by local jurisdiction, the ability to access property tax databases is inconsistent. These inconsistencies can introduce both technical and logistical issues. For some jurisdictions, property data is available in GIS (Geographical Information System) format, typically for fee (as an example, Scottsdale, Ariz. charges $38,000 for a citywide license to their GIS-based parcel data). For others, property data is limited to paper or raster scans and thus not usable as source for geocoding.
Accordingly, there is a need for geocoding methods that obviate one or more of the above shortcomings and disadvantages.